package basis.netease.hard;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;

/**
 * 7-1 按格式合并两个链表
 * 给定两个链表L1=a1→a2→⋯→an−1→an 和L2=b1→b2→⋯→bm−1→bm，其中n≥2m。
 * 需要将较短的链表L2反转并合并到较长的链表L1中
 * 使得合并后的链表如下形式：a1→a2→bm→a3→a4→bm−1→…
 * 合并规则：在长链表中每隔两个元素，将短链表中的元素倒序插入。
 * 例如：给定一个较长链表1→2→3→4→5，另外一个较短链表6→7，需要输出1→2→7→3→4→6→5
 * 输入格式:
 * 第一行包含两个链表的第一个节点地址（不确定哪个链表更长），以及两个链表的总节点数N(≤100000)。
 * 节点地址用一个 5 位非负整数表示（可能有前导 0），空地址 NULL 用 −1 表示。
 * 例如：00100 01000 7。其中00100表示第一个链表的首个节点地址，01000表示第二个链表的首个节点地址，7表示两个链表的总节点数。
 * 接下来N行，每行描述一个节点的信息，格式如下：
 * Address Data Next
 * 其中 Address 是节点地址，Data 是一个绝对值不超过100000的整数，Next 是下一个节点的地址。
 * 保证两个链表都不为空，且较长的链表至少是较短链表长度的两倍。
 * 输出格式:
 * 对于每个测试用例，按顺序输出合并后的结果链表。每个结点占一行，按输入的格式输出。
 * 输入样例:
 * 在这里给出一组输入。例如：
 * 00100 01000 7
 * 01000 1 02233
 * 02233 2 34891
 * 34891 3 10086
 * 10086 4 00033
 * 00033 5 -1
 * 00100 6 00001
 * 00001 7 -1
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 01000 1 02233
 * 02233 2 00001
 * 00001 7 34891
 * 34891 3 10086
 * 10086 4 00100
 * 00100 6 00033
 * 00033 5 -1
 */
public class Main_1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        String firstNode1 = input[0];
        String firstNode2 = input[1];
        int nodeCount = Integer.parseInt(input[2]);
        Map<String, Node> nodeMap = new HashMap();
        for (int i = 0; i < nodeCount; i++) {
            input = scanner.nextLine().split(" ");
            nodeMap.put(input[0], new Node(input[0], input[1], input[2]));
        }
        LinkedList<Node> nodeList1 = new LinkedList();
        Node node1 = nodeMap.get(firstNode1);
        while (node1 != null) {
            nodeList1.add(node1);
            node1 = nodeMap.get(node1.next);
        }
        LinkedList<Node> nodeList2 = new LinkedList();
        Node node2 = nodeMap.get(firstNode2);
        while (node2 != null) {
            nodeList2.add(node2);
            node2 = nodeMap.get(node2.next);
        }
        // 确保nodeList1为长，nodeList2为短
        if (nodeList1.size() < nodeList2.size()) {
            LinkedList<Node> nodeList3 = nodeList2;
            nodeList2 = nodeList1;
            nodeList1 = nodeList3;
        }
        // nodeList1为长，nodeList2为短
        int index = 2;
        while (!nodeList2.isEmpty()) {
            nodeList1.add(index, nodeList2.pollLast());
            index = Math.min(index + 3, nodeList1.size());
        }
        for (int i = 0; i < nodeList1.size(); i++) {
            Node current = nodeList1.get(i);
            if (i + 1 < nodeList1.size()) {
                Node next = nodeList1.get(i + 1);
                System.out.println(current.address + " " + current.data + " " + next.address);
                continue;
            }
            System.out.println(current.address + " " + current.data + " -1");
        }
    }

    public static class Node {
        String address;
        String data;
        String next;

        public Node(String address, String data, String next) {
            this.address = address;
            this.data = data;
            this.next = next;
        }
    }

}
